/*
 * @Author: wuqingchun
 * @Date: 2024-07-30 13:52:41
 * @Description: 
 * @LastEditors: wuqingchun
 * @LastEditTime: 2024-07-30 19:57:29
 */

#include <stdio.h>
#include <stdlib.h>

#include "min_heap.h"

static int __minheap_Extend(MIN_HEAP_S* pstMinHeap)
{
    void** ppNodes = (void**)realloc(pstMinHeap->ppNodes, sizeof(void*) * pstMinHeap->ulCapacity * 2);
    if (ppNodes == NULL)
    {
        return -1;
    }

    pstMinHeap->ppNodes = ppNodes;

    return 0;
}

int MINHEAP_Init(MIN_HEAP_S* pstMinHeap, size_t ulInitCapacity, MINHEAP_CMP_NODE_PF pfCmp)
{
    void** ppNodes = (void**)malloc(sizeof(void*)*ulInitCapacity);
    if (ppNodes == NULL)
    {
        return -1;
    }

    pstMinHeap->ppNodes = ppNodes;
    pstMinHeap->ulCapacity = ulInitCapacity;
    pstMinHeap->ulSize = 0;
    pstMinHeap->pfCmp = pfCmp;

    return 0;
}

void MINHEAP_Fini(MIN_HEAP_S* pstMinHeap)
{
    if (pstMinHeap != NULL && pstMinHeap->ppNodes)
    {
        free(pstMinHeap->ppNodes);

        pstMinHeap->ppNodes = NULL;
        pstMinHeap->ulCapacity = 0;
        pstMinHeap->ulSize = 0;
        pstMinHeap->pfCmp = NULL;
    }
}

int MINHEAP_Push(MIN_HEAP_S* pstMinHeap, void* pNode)
{
    if (pstMinHeap->ulSize == pstMinHeap->ulCapacity)
    {
       return __minheap_Extend(pstMinHeap);
    }

    size_t ulNewIndex = pstMinHeap->ulSize;
    size_t ulParentIdx = (ulNewIndex - 1) / 2;

    while (ulNewIndex > 0 && pstMinHeap->pfCmp(pNode, pstMinHeap->ppNodes[ulParentIdx]) < 0)
    {
        pstMinHeap->ppNodes[ulNewIndex] = pstMinHeap->ppNodes[ulParentIdx];
        ulNewIndex = ulParentIdx;
        ulParentIdx = (ulNewIndex - 1) / 2;
    }

    pstMinHeap->ppNodes[ulNewIndex] = pNode;
    pstMinHeap->ulSize++;

    return 0;
}

void MINHEAP_Show(MIN_HEAP_S* pstMinHeap)
{
    for (size_t ulIdx = 0; ulIdx < pstMinHeap->ulSize; ulIdx++)
    {
        printf("%d ", (int)(long)pstMinHeap->ppNodes[ulIdx]);
    }

    printf("\n");
}

void* MINHEAP_Pop(MIN_HEAP_S* pstMinHeap)
{
    if (pstMinHeap->ulSize == 0)
    {
        return NULL;
    }

    void* pTop = pstMinHeap->ppNodes[0];
    pstMinHeap->ppNodes[0] = pstMinHeap->ppNodes[pstMinHeap->ulSize - 1];
    pstMinHeap->ulSize--;

    size_t ulIdx = 0;
    size_t ulLeftIdx = 2 * ulIdx + 1;
    size_t ulRightIdx = ulLeftIdx + 1;
    
    while (ulLeftIdx < pstMinHeap->ulSize)
    {
        size_t ulMinIdx = ulIdx;
        if (pstMinHeap->pfCmp(pstMinHeap->ppNodes[ulLeftIdx], pstMinHeap->ppNodes[ulMinIdx]) < 0)
        {
            ulMinIdx = ulLeftIdx;
        }
        
        if (ulRightIdx < pstMinHeap->ulSize && 
            pstMinHeap->pfCmp(pstMinHeap->ppNodes[ulRightIdx], pstMinHeap->ppNodes[ulMinIdx]) < 0)
        {
            ulMinIdx = ulRightIdx;
        }

        if (ulMinIdx == ulIdx)
        {
            break;
        }

        void* pTmp = pstMinHeap->ppNodes[ulIdx];
        pstMinHeap->ppNodes[ulIdx] = pstMinHeap->ppNodes[ulMinIdx];
        pstMinHeap->ppNodes[ulMinIdx] = pTmp;
        ulIdx = ulMinIdx;

        ulLeftIdx = 2 * ulIdx + 1;
        ulRightIdx = ulLeftIdx + 1;
    }

    return pTop;
}

int __CmpNode(void* pNode1, void* pNode2)
{
    int iNode1 = (int)(long)pNode1;
    int iNode2 = (int)(long)pNode2;

    return iNode1 - iNode2;
}
#if 0
int main(int argc, char** argv)
{
    MIN_HEAP_S stMinHeap;

    MINHEAP_Init(&stMinHeap, 8, __CmpNode);

    int iValue = 8;
    MINHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 2;
    MINHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 6;
    MINHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 4;
    MINHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 3;
    MINHEAP_Push(&stMinHeap, (void*)(long)iValue);
    iValue = 9;
    MINHEAP_Push(&stMinHeap, (void*)(long)iValue);

    iValue = 7;
    MINHEAP_Push(&stMinHeap, (void*)(long)iValue);

    MINHEAP_Show(&stMinHeap);

    void* pData = MINHEAP_Pop(&stMinHeap);
    while (pData != NULL)
    {
        MINHEAP_Show(&stMinHeap);
        //printf("%d ", (int)(long)pData);
        pData = MINHEAP_Pop(&stMinHeap);
    }

    printf("\n");

    return 0;
}
#endif